/*
*	前缀和
*/


//前缀和
//https://www.nowcoder.com/practice/acead2f4c28c401889915da98ecdc6bf?tpId=230&tqId=2021480&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196
// int main() {
//     int n = 0, q = 0;
//     while (cin >> n >> q) {
//         vector<int> arr(n);
//         for (int i = 0; i < n; ++i) cin >> arr[i];

//         vector<long long> sumi(n);
//         sumi[0] = arr[0];
//         for (int i = 1; i < n; ++i) sumi[i] = sumi[i - 1] + arr[i];

//         for (int i = 0; i < q; ++i)
//         {
//             int b = 0, e = 0;
//             cin >> b >> e;
//             if (b == e) cout << arr[b-1] << endl;
//             else cout << sumi[e - 1] - (b == 1?0:sumi[b - 2]) << endl;
//         }
//     }
// }


//二维前缀和
//https://www.nowcoder.com/practice/99eb8040d116414ea3296467ce81cbbc?tpId=230&tqId=2023819&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196
// int main() {
//     int n,m,q;
//     while (cin >> n >> m >> q) {
//         vector<vector<int>> arr(n+1,vector<int>(m+1));
//         for(int i = 1;i<=n;++i)
//             for(int k = 1;k<=m;++k) 
//                 cin>>arr[i][k];

//         //sumi[i][k] 表示 sumi[0][0]~sumi[i][k] 所有数之和
//         vector<vector<long long>> sumi(n+1,vector<long long>(m+1));
//         for(int i = 1;i<=n;++i)
//             for(int k = 1;k<=m;++k)
//                 sumi[i][k]=sumi[i][k-1]+sumi[i-1][k]+arr[i][k]-sumi[i-1][k-1];

//         int x1,y1,x2,y2;
//         for(int i = 0;i<q;++i)
//         {
//             cin>>x1>>y1>>x2>>y2;
//             cout<<(sumi[x2][y2]-sumi[x1-1][y2]-sumi[x2][y1-1]+sumi[x1-1][y1-1])<<endl;
//         }

//     }
//     return 0;
// }


//寻找数组的中心下标
//https://leetcode.cn/problems/find-pivot-index/submissions/
// class Solution {
// public:
//     int pivotIndex(vector<int>& nums) {
//         int n = nums.size();
//         vector<int> f(n+1),g(n+1);

//         for(int i = 1;i<=n;++i) f[i] = f[i-1]+nums[i-1];
//         for(int i = n-2;i>=0;--i) g[i] = g[i+1]+nums[i+1];

//         for(int i = 0;i<n;++i)
//             if(f[i] == g[i]) return i;

//         return -1;
//     }
// };


//除自身以外数组的乘积
//https://leetcode.cn/problems/product-of-array-except-self/
// class Solution {
// public:
//     vector<int> productExceptSelf(vector<int>& nums) {
//         int n = nums.size();
//         //f表示从前往后遍历的结果 g表示从后往前遍历的结果
//         //f表示左边[0,i-1]的乘积 g表示右边[i+1,n-1]的乘积
//         vector<int> f(n, 1), g(n, 1);
//         for (int i = 1; i < n; ++i)
//             f[i] = f[i - 1] * nums[i-1];
//         for (int i = n - 2; i >= 0; --i)
//             g[i] = g[i + 1] * nums[i+1];

//         vector<int> ret(n);
//         for (int i = 0; i < n; ++i)
//             ret[i] = f[i] * g[i];
//         return ret;
//     }
// };


//和为K的子数组
//https://leetcode.cn/problems/subarray-sum-equals-k/description/
// class Solution {
// public:
//     int subarraySum(vector<int>& nums, int k) {
//         unordered_map<int,int> hash;
//         //sum[i] 表示0~i位置所有数之和 我们只需要去 0~(i-1) 中查找 sum[i]-k 出现了几次即可
//         hash[0] = 1; //如果整个数组和为k 则有一个数组

//         int sum = 0,ret = 0;
//         //sum表示当前第0~i个值的和 我们将sum分为 (0~sum-k) (sum-k~sum)
//         //其中 (sum-k~sum)=k 而我们只需要获取(0~sum-k) 也就是 sum[0]~sum[i-1]-k 的值 这个值可能正好是0~sum(sum-k=0) 也可能是中间段
//         for(const auto& n:nums)
//         {
//             //sum 走到第i个位置 表示0~i的所有数之和
//             sum += n;
//             //如果 存在 sum[i]-k 则加上其出现次数
//             if(hash.count(sum-k)) ret += hash[sum-k];
//             ++hash[sum]; //将sum记入
//         }
//         return ret;
//     }
// };


//和可被K整除的子数组
//https://leetcode.cn/problems/subarray-sums-divisible-by-k/
// class Solution {
// public:
//     int subarraysDivByK(vector<int>& nums, int k) {
//         //同余定理
//         // (a-b)%c=k  则 a%c=b%c=k
//         //(a+k*p)%k = a%k
//         //C++存在负数取余仍然为复数的情况 我们进行修正 即 (a%k+k)%k
//         unordered_map<int,int> hash;
//         int ret = 0,sum = 0;
//         hash[0] = 1;
//         //我们将和sum(表示 0~i 个数之间的和) 化为两段 sum[0]~sum[i-1] sum[i+1]+sum[n-1]
//         //如果存在 (sum-x)%k=0 则 sum%k=x%k 我们只需要寻找有多少个和为x的子数组即可
//         for(auto& n:nums)
//         {
//             sum += n;
//             int mod = (sum%k+k)%k;
//             if(hash.count(mod)) ret += hash[mod];
//             ++hash[mod];
//         }
//         return ret;
//     }
// };


//连续数组
//https://leetcode.cn/problems/contiguous-array/description/
// class Solution {
// public:
//     int findMaxLength(vector<int>& nums) {
//         //将0设为-1 则当含有相同的1和0的个数时 数组和为0
//         unordered_map<int,int> hash;
//         int ret = 0,sum = 0,n = nums.size();
//         hash[0] = -1; //当0~n之间和为0 我们需要去 ~ -1 之间寻找一个区间 而0之前的那个下标就是 -1 这样才能正确计算
//         for(int i = 0;i<n;++i)
//         {
//             sum += (nums[i]==0?-1:1);
//             if(hash.count(sum)) ret = max(ret,i-hash[sum]);
//             else hash[sum] = i; //不重复存入 始终只存 最前面那个和为0的 0~i的下标 这样就能存更长的下标
//         }
//         return ret;
//     }
// };


//矩阵区域和
//https://leetcode.cn/problems/matrix-block-sum/submissions/
// class Solution {
// public:
//     vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
//         int m = mat.size(),n = mat[0].size();
//         vector<vector<int>> ans(m+1,vector<int>(n+1));

//         for(int i = 1;i<=m;++i)
//             for(int j = 1;j<=n;++j)
//                 ans[i][j] = ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1]+mat[i-1][j-1];
            
//         vector<vector<int>> ret(m,vector<int>(n));

//         for(int i = 0;i<m;++i)
//             for(int j = 0;j<n;++j)
//             {
//                 //由于我们返回m*n的数组 但是ans是m+1*n+1 所以查询下标+1
//                 int x1 = max(0,i-k)+1,y1 = max(0,j-k)+1;
//                 int x2 = min(m-1,i+k)+1,y2 = min(n-1,j+k)+1;
//                 ret [i][j] = ans[x2][y2]-ans[x1-1][y2]-ans[x2][y1-1]+ans[x1-1][y1-1];
//             }

//         return ret;
//     }
// };


